In recent years, consumers have been provided with a multitude of devices using electronic maps for a variety of different purposes. For example, electronic maps may be used in electronic devices to facilitate navigation, locate places of interest, find addresses, etc. When an electronic device is used to facilitate navigation, the device may use, for example, GPS (Global Positioning System) signal reception and processing functionality. Examples of electronic devices with navigational capabilities and systems used by consumers include in-vehicle navigation systems that enable vehicle operators to navigate over streets, roads, airways, shipping lanes and the like; hand-held devices such as personal digital assistants (“PDAs”), personal navigation devices (PNDs), and cell phones or other types of mobile devices that can do the same; desktop applications, and internet applications in which users can generate maps showing desired places. The common aspect in all of these and other types of devices and systems is a map database of geographic features, vectors and attributes, and software to access, manipulate and navigate the map database in response to user inputs.
Electronic maps may be virtual environments that model ‘real-world’ 2 or 3 dimensional regions using data points corresponding to physical locations. For example, an electronic map may simulate a part of the ocean, a portion of the Earth's surface or the airspace above the earth. In order to model such large regions, each virtual environment may include hundreds of millions of data points. Each data point generally corresponds to a 2 or 3 dimensional point relative to a fixed reference.
An electronic device directed at, for example, ground vehicles may include an electronic map having travelable routes for one or more continents. Generally, the electronic device will display a portion of the electronic map, including travelable routes, as a graphic using a compressed scale. Further, the electronic device will often display non-route features as well, for example buildings, landmarks, geological features, etc.
Positional data representing the routes and non-route features may be accurate, for example, to 3 meters or less. However, the accuracy and detail of the data may depend on, for example, the amount of data collected for a particular location and the time the data was collected.
A time in which data is collected affects the accuracy of an electronic map because the world is not a static construct. Even if a comprehensive map database is compiled that includes every possible characteristic of route, new routes may be built, existing routes may be removed and/or existing routes may shift due to, for example, new building construction. Existing routes may also change temporarily, such as when a road is rebuilt and a detour is created. As a result, varying attempts have been made to iteratively collect data over time in order to keep electronic maps current.
Recently it has been proposed that electronic maps may be kept current by utilizing the cooperation of electronic device users. With the permission of the device user, temporal positional data, referred to as a probe trace, may be collected by, for example, recording sequential positional data of an electronic device over one or more periods of time. Probe trace data may be continuously collected and uploaded to a central server.
Probe traces consisting of a series of sequential location measurements that represent the movement of a vehicle or pedestrian using a navigation device may be used to infer and subsequently map the location of a road centerline or pathway being traveled. Although a GPS or other location measuring sensor used in the navigation device may be of poor accuracy and/or precision, by statistically averaging probe traces from several vehicles traversing the same road, the precision and accuracy of the inferred road centerline may be improved.
Most statistical models used to determine a road centerline from numerous probe traces may utilize Gaussian statistics (a normal distribution). A normal distribution implies that most probe traces will fall near the centerline of the actual road or lane being traveled. Inherent in Gaussian statistics is that random noise (e.g. error in location measurements) may be normally or randomly distributed around a mean. However, with respect to GPS and other forms of position measurement, error may not be normally distributed and Gaussian statistics may not be valid.
For example, GPS signals require line-of-sight between the satellites and the receiver. If there is an obstruction that prohibits a line-of-sight view and a further obstruction acts as a reflector, a systematic (non-Gaussian) error may occur in positional measurements. The systematic error may be due to an increase in the time required for the satellite signal to reach the receiver.
FIGS. 12A and 12B are example diagrams illustrating an “urban canyon effect” which may result in sequential positional data including non-Gaussian error. FIG. 12A is a diagram illustrating GPS signal propagation and a multi-path phenomena. FIG. 12B is a diagram illustrating positional measurement error due to the multi-path phenomena.
Referring to FIG. 12A, a satellite signal 1210 from a GPS satellite 1200 may be received at a GPS antenna 1220. The satellite signal 1210 may be unimpeded and may not cause an error in a positional measurement. A satellite signal 1240 from a GPS satellite 1230 may be obstructed by an obstacle 1250. The satellite signal 1240 may be reflected from a GPS multi-path object 1260 and received by the GPS antenna 1220. The reflected satellite signal 1240 may travel a longer distance than if the satellite signal 1240 is unimpeded. An error may occur in a positional measurement due to the time delay in receiving the reflected satellite signal 1240 due to the longer distance travelled by the reflected satellite signal 1240.
Referring to FIG. 12B, a series of real positions 1270 are shown. The real positions 1270 may correspond to geographic locations at which positional measurements may be recorded. DGPS positions 1280 may be positions corresponding to GPS positional data recorded for real positions 1270. The DGPS positions 1280 may not coincide with the real positions 1270 due to, for example, multi-path error in the positional measurements. Positions DGPS 1290 illustrate a case where the real positions 1270 and positions corresponding to GPS measurement data coincide (e.g., no error). Accordingly, FIG. 12B may demonstrate non-Gaussian error in positional measurements.